16.5 オンザフライマーキング

オンザフライ GC

ミューテータを同時にすべて止めない GC

コレクタは1つ1つのミューテータに対し、順番にソフトハンドシェークで対応

それぞれのミューテータスレッドに対し、非同期に、１つずつ都合のいいポイントでうまく停止するよう促す

停止後は、そのスレッドの状態を抽出（＆変更）し、スレッドを解放して実行を続けさせる

スタックバリアを用いると、ミューテータが今必要なトップフレーム部分だけに注力できて早い！

オンザフライGC 用のライトバリア

オンザフライ GC における同期操作には注意が必要

オンザフライ GC では白いスタックも存在しうるため。具体的には：

1. 全スレッドの走査を終えて追跡が始まる前に、ヒープへ黒いオブジェクトが入るかも

新しいオブジェクトは黒で割り付けられるから

2. X を書き換えて Y への参照を持つようにする（挿入バリアは無いのでX, Y はそれぞれ黒、白のまま）

3. スタック2の Y への参照を削除（スタックには削除バリアがないのでこのまま）

4. 黒 (X) が白 (Y) を指してしまう

https://gyazo.com/f31e81f5714e01d9b62df5672a006826

要するに、スイープの直後には、スレッド2のルートの色付けが行われるが、その過程でルートから直接指されるオブジェクト(Y)がまだ色付けが済んでいない状態が発生しうる。そのタイミングでルートが書き換わってYが宙に浮くと、不変条件が壊れる。

コンパイラが挿入するコード片

コンパイラが協力してくれないときは OS の力を借りたりする

a fragment of code emitted by the compiler immediately before every store operation to ensure that (e.g.) generational invariants are maintained

Doligez-Leroy-Gonthier 方式

注意：論文を読まないとわかりません

コレクタが各フェーズにおいて何をするのか、本からは何もわからない

走査で何をするのかがわからない(実はマーキングとは分かれている)

ML 向けの GC

共有ヒープと、それとは別にプライベートなスレッドローカルヒープを用いる

あるスレッドのためだけに割り付けられた、非共有データを分離して管理するもの

グローバル -> プライベートへの参照が発生しないようにする

そういうときは、グローバルにそのデータ（の到達可能性に関する推移的閉包）をコピーする

MLなので、グローバルにあるのは参照と参照が指すオブジェクトの推移的閉包

ML ならほとんど immutable なので(参照が少ないので)、このコストによる影響は小さい

スレッドローカルヒープにより、そのヒープを所有するミューテータだけ停止して GC できる

stop-and-copy collector って書いてあった、あと細かいけど世代別らしい

並行マークスイープ GC は共有ヒープに対し用いられる

個々のスレッドからの参照を更新しなくてよい

移動式じゃないって意味と思われる

本手法では Async/Sync1/Sync2 という3状態でコレクタが動作する

論文によると、コレクタとミューテータの初期状態はすべて Async っぽい

Sync1 : "mutators will only update fields with pointers to object that will be marked in this cycle"

Sync2 : "mutators will only update fields that point to objects that will be marked in this cycle"

定常状態とは？-> とりあえず全 status は Async ではありそう

定常状態で GC が起動すると、ミューテータスレッドを灰色から黒に遷移させるソフトハンドシェークを連続して行う

全スレッドは各々、自分がコレクションの状態をどう見ているかをプライベートな状態変数を用いて管理

GC サイクルの開始時に、コレクタが自身のステータスを Sync1 にセット

ミューテータスレッドはそれを確認し、Sync1 ハンドシェークを経て自身の状態を Sync1 に更新

ミューテータはポインタフィールドへの書き込み中や割り付け中ではハンドシェークを無視

これらの操作をフェーズの変更に対し不可分にする

ミューテータスレッドは、ハンドシェークへの確認応答後、16-3 (a) のライトバリアを用いて実行を続行

ミューテータが色付する際、色付けしたオブジェクトを直接コレクタのワークリストへ追加しない

単に白いオブジェクトを明示的に灰色にし、グローバルな dirty 変数をリセット (true にするってこと？)

後でコレクタに新しい灰色オブジェクトを走査させる

この方法ではミューテータとコレクタが明示的に同期する必要はない

Scan の終了判定の時、最悪の場合ヒープ全体を再走査して灰色オブジェクトを探す必要がある

変数がほぼ immutable な ML では書き換えは稀なので、深刻な問題ではない

この時点では灰色ミューテータは白で割り付けしているが、これは GC サイクル以前からと同じ

すべてのスレッドが Sync1 ハンドシェークの確認を行った時、コレクタは Sync1 フェーズとなる

Algorithm 16-3 (a)

code:python

def Write_Sync(src, i, new):

shade(old)

shade(new)

Sync1 フェーズ

コレクタスレッドは自身の status を Sync2 に更新

同様に1ラウンドのハンドシェークを行い、Sync2 フェーズへ移行を進める

ライトバリア 16-3(a) は、ハンドシェークに関しては不可分だが、ミューテータ間の同期はとってない

Sync2 フェーズ（Sync2 ハンドシェーク）をなくすと以下の手順で問題が生じる

B が X を load する （リードバリアはないので X には当然色がつかない

Write 前なので、X は B のルートによって参照されているとはまだ言えない？

このタイミングでコレクタが Scan を開始すると、X がゴミ扱いされて回収されちゃう

B は X を load してこれから使うので、困る

Sync2 ハンドシェークによって以下が保証できる

"all traps laid during the Sweep step are tripped before the Mark step begins"

Sync2 フェーズ

コレクタスレッドは自身の status を Async に更新

Async ハンドシェークにより Async フェーズへの移行を進める

各ミューテータは、Async ハンドシェークを確認したら、応答する前に marking を行う

自身のルートを走査して、ミューテータの色を黒にする

その後黒によるオブジェクトの割り付けを開始し、標準のスナップショットバリアを使う状態に戻す

色付したオブジェクトが走査境界の後方にある場合はコレクタに再走査させる：algorithm 16-3 (b)

Algorithm 16-3 (b)

Async バリア

code:python

def Write_Async(src, i, new):

if not isBlack(old):

shade(old)

if old <= scanned:

dirty = True

Async フェーズ

マーキングが終わって、全ミューテータからの確認応答があった後のフェーズ

この時点で全ミューテータは黒になっている

コレクタの仕事は Scan （再走査）と Sweep

スイープ済みのメモリから割り当てる場合は白で割り付け

このサイクルではすでに白と記録済みになるようにするため

スイープが済んでいない場合は黒で割り付け

フリーリストに回収してしまうことを避けるため

コレクタが現在スイープ中の場所の場合には灰色で割り付け

スイーパとの境界における競合を避けるため

表16-2 見るよりこっち見るほうが良さそうな気がします

sweep : Sweep ステップの進捗（アドレス）を表すポインタ

ミューテータは、書き込み＆割り込み時に swept をテストし、Sweep 中に浮遊ゴミが生成されないようにする

scanned : Scan ステップの進捗（アドレス）を表すポインタ

ミューテータは dirty をリセットする前に scanned をチェックして、spurious scan が起こらないようにする

https://gyazo.com/82fb090ec0c68e5e8665ca3abbdfc5f7

Java 用 Doligez-Leroy-Gonthier

ML 違って書き換え頻度が極めて高く、弱参照やファイナライゼーションという機能もあるので、それに対応

（当時は）immutable オブジェクトはサポートされていなかったので、スレッドローカルなヒープは用いずに、単にグローバルな共有ヒープをオンザフライ GC する

ミューテータのルートをストップザワールドの停止なしで抽出する手法

基本的には、ある時点のスナップショットに対してコレクタがマークする方法

スナップショットの状態からミューテータが変更する際に、変更前の状態をスレッドローカルバッファに記録することで、過去の時点のスナップショットに対するマークができるようにする

ミューテータの変更がなければ、単にコレクタが普通にマークするだけ

コレクタはソフトハンドシェークによってスレッドローカルバッファにアクセスし、バッファが空になればマークが終わったことになる

詳細は 18.5 でやるらしいので以下は適当に…

最初のハンドシェークの後、削除バリアを各ミューテータがオンにするまでは、ミューテータは Dijkstra スタイルのインクリメンタルアップデート挿入バリアを実行

DLG（略）法と同様

ミューテータのスナップショットを集める前に、気づかないうちにポインタを伝搬するのを防ぐ

これらの覗き見ストアもミューテータのルートになる

覗き見ストアは、全スレッドがスナップショットのロギングを開始するとオフにする